1. Field of the Invention
The present invention relates generally to a communication system using linear block codes, and more particularly, to a channel coding and decoding method and apparatus for generating specific types of linear block codes
2. Description of the Related Art
A Low-Density Parity-Check (LDPC) code, which is a type of linear block code, may be expressed using a bipartite graph, which is generally defined as a parity check matrix and referred to as a Tanner graph. The bipartite graph is a graph whose vertexes are divided into two different types. The LDPC code is expressed with a bipartite graph including vertexes called variable nodes and check nodes. The variable nodes correspond to coded bits on a one-to-one basis.
FIG. 1 illustrates an example of a parity check matrix H1 of an LDPC code including 4 rows and 8 columns.
Referring to FIG. 1, the parity check matrix H1 generates a codeword with a length of 8 because it has 8 columns. A code generated using the parity check matrix H1 is an LDPC code, and its columns correspond to 8 coded bits.
FIG. 2 illustrates a Tanner graph corresponding to the parity check matrix H1 in FIG. 1.
Referring to FIG. 2, the Tanner graph for the LDPC code includes 8 variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216, and 4 check nodes 218, 220, 222, and 224. An i-th column and a j-th row of the parity check matrix H1 of the LDPC code correspond to a variable node X, and a j-th check node, respectively. A value of 1 (i.e., a non-zero value) in a point where an i-th column and a j-th row of the parity check matrix H1 of the LDPC code cross each other, indicates the existence of an edge connecting the variable node Xi to the j-th check node on the Tanner graph in FIG. 2.
In the Tanner graph for the LDPC code, a degree of a variable node or a check node indicates the number of edges connected to the node, and is equal to the number of non-zero entries in a column or a row corresponding to the node in the parity check matrix. For example, in FIG. 2, degrees of the variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216 are 4, 3, 3, 3, 2, 2, 2, and 2, respectively, and degrees of the check nodes 218, 220, 222, and 224 are 6, 5, 5, and 5, respectively. The numbers of non-zero entries in columns of the parity check matrix H1 in FIG. 1, which correspond to the variable nodes in FIG. 2, are equal to the degrees 4, 3, 3, 3, 2, 2, 2, and 2 of the variable nodes on a one-to-one basis, and the numbers of non-zero entries in rows of the parity check matrix H1 in FIG. 1, which correspond to the check nodes in FIG. 2, are equal to the degrees 6, 5, 5, and 5 of the check nodes on a one-to-one basis.
Therefore, it can be understood that an i-th codeword bit ci, an i-th column hi in the parity check matrix, and an i-th variable node xi on the Tanner graph correspond to one another.
FIG. 3 is a diagram schematically illustrating a structure of an LDPC code.
Referring to FIG. 3, N1 represents a length of an LDPC codeword, and is equal to a length of the parity check matrix. K1 represents a length of an information word, and is equal to a length of an information part of the parity check matrix. (N1−K1) represents a length of parity bits, and is equal to a length of a parity part of the parity check matrix. In addition, integers M1 and q are determined to meet q=(N1−K1)/M1. K1/M1 may also be an integer. For convenience, the parity check matrix in FIG. 3 will be assumed to be a first parity check matrix H1.
Positions with a weight of 1 in the portion of K1-th to (N1−1)-th columns, which corresponds to the parity part in the parity check matrix of FIG. 3, have a dual diagonal structure. Therefore, all columns corresponding to the parity part, except for the (N1−1)-th column, have a degree of 2, and the (N1−1)-th column has a degree of 1.
A structure of the portion of 0-th to (K1−1)-th columns, which corresponds to the information part of the parity check matrix, is made according to the following rules.
Rule 1: A total of K1/M1 column groups are made by grouping K1 columns corresponding to the information word in the parity check matrix into a plurality of groups each including M1 columns. Columns in each column group are made according to the following Rule 2.
Rule 2: First, a position with a weight of 1 in a 0-th column in an i-th column group (where i=0, 1, . . . , K1/M1−1) is determined. Second, a degree of an 0-th column in an i-th column group is defined as Di. Assuming that positions of rows with a weight of 1 are Ri,0(1), Ri,0(2), . . . , Ri,0(Di), a position Ri,j(k) (for k=1, 2, . . . , Di) of a row with a weight of 1 in a j-th column (where j=1, 2, . . . , M1−1) in an i-th column group is defined as shown in Equation (1) below.Ri,j(k)=Ri,(j−1)(k)+q mod(N1−K1)k=1,2, . . . , Di,i=0,1, . . . , K1/M1−1,j=1,2, . . . , M1−1  (1)
According to Rule 2, all columns in an i-th column group (where i=0, 1, . . . , K1/M1−1) have the same degree of Di.
For a better understanding of the LDPC code as illustrated in FIG. 3, which stores information about the parity check matrix according to the above Rule 2, the following specific example will be considered.
In a parity check matrix with N1=30, K1=15, M1=5 and q=3, for 0-th columns in 3 column groups, 3 sequences regarding positions of rows with a weight of 1 may be represented as follows. These sequences will be referred to as ‘weight-1 position sequences’.R1,0(1)=1,R1,0(2)=2,R1,0(3)=8,R1,0(4)=10,R2,0(1)=0,R2,0(2)=9,R2,0(3)=13,R3,0(1)=0,R3,0(2)=14.
For convenience, as to information about rows with a weight of 1 for 0-th columns in the above column groups, only associated position information will be represented on a column group basis as follows:
0 1 2 8 10
0 9 13
0 14
In other words, a sequence of an i-th column group sequentially represents information about rows with a weight of 1 in a 0-th column in an i-th column group.
The LDPC code may be coded generally by a formula in which the results of binary multiplication on the parity check matrix H and the codeword c become a zero (0) matrix.
FIG. 4 is a diagram illustrating an example of a parity check matrix of an LDPC code.
By constructing a parity check matrix using the information associated with the above specific example and Rules 1 and 2, an LDPC code having the same concept as the LDPC code illustrated in FIG. 3 may be generated as illustrated in FIG. 4.
Coding Method of LDPC Code
For convenience of description, information bits (or information word bits) with a length of K1 are represented as (i0, i1, . . . , iK1−1), and parity bits with a length of (N1−K1) are represented as (p0, p1, . . . , pN1−K1−1). An LDPC code has the characteristics of N1=16200, K1=10800, M1=360, and q=15.
Step 1: A controller initializes parity bits, as follows:p0=p1= . . . =pN1−K1−1=0
Step 2: The controller reads information about rows with a weight of 1 in a 0-th column in a first column group of an information part from stored information about the parity check matrix, as follows:R1,0(1)=0,R1,0(2)=2084,R1,0(3)=1613,R1,0(4)=1548,R1,0(5)=1286,R1,0(6)=1460,R1,0(7)=3196,R1,0(8)=4297,R1,0(9)=2481,R1,0(10)=3369,R1,0(11)=3451,R1,0(12)=4620,R1,0(13)=2622
Using the read information and an information bit i0, specific parity bits px are updated as shown in Equation (2) below.p0=p0⊕i0,p2084=p2084⊕i0,p1618=p1618⊕i0,p1548=p1548⊕i0,p1286=p1286⊕i0,p1460=p1460⊕i0,p8196=p8196⊕i0,p4297=p4297⊕i0,p2481=p2481⊕i0,p3369=p3369⊕i0,p3451=p3451⊕i0,p4620=p4620⊕i0,p2622=p2622⊕i0  (2)
In Equation (2), x represents R1,0(k) for k=1, 2, . . . , 13, ⊕ represents binary addition, and px=px⊕i0 may be expressed as px←px⊕i0.
Step 3: For the next 359 information bits i1, i2, . . . , i359 following the information bit i0, values are calculated using Equation (3) below.{x+(m mod M1)×q} mod(N1−K1),m=1,2, . . . , 359  (3)
In Equation (3), x represents R1,0(k) for k=1, 2, . . . , 13. It is to be noted that Equation (3) is equal in concept to Equation (1).
Next, a similar operation to Equation (2) is performed using the values calculated in Equation (3). In other words, for im, p{x+(m mod M1×q)} mod(N1−K1) is updated. For example, for m=1, i.e., for i1, p(x+q)mod(N1−K1) is updated as shown in Equation (4) below.p15=p15⊕i1,p2099=p2099⊕i1,p1628=p1628⊕i1,p1568=p1568⊕i1,p1301=p1301⊕i1,p1475=p1475⊕i1,p3211=p3211⊕i1,p4312=p4312⊕i1,p2496=p2496⊕i1,p3384=p3384⊕i1,p3466=p3466⊕i1,p4635=p4635⊕i1,p2637=p2637⊕i1  (4)
In Equation (4), q=15. The above process is performed in the same way, for m=1, 2, . . . , 359.
Step 4: As in Step 2, for an information bit i361, information of R2,0(k) (for k=1, 2, . . . , 13) is read and a specific px is updated, where x represents R2,0(k). For the next 359 information bits i361, i362, . . . , i719 following the information bit i360, p{x+(m mod M1×q)} mod(N1−K1) (for m=361, 362, . . . , 719) is updated by applying Equation (3) in a similar way.
Step 5: For all of 360 information bit groups, Steps 2, 3 and 4 are repeated. Finally, parity bits are determined using Equation (5) below.pi=pi⊕pi−1,i=1,2, . . . , N1−K1−1  (5)
In Equation (5), Pi represents LDPC-coded parity bits.
In the above LDPC coding method, coding is performed through Steps 1 to 5.
In order to apply an LDPC code to an actual communication system, the LDPC code should be designed to be appropriate for a data rate required in the communication system. Particularly, not only in an adaptive communication system using Hybrid Automatic Retransmission reQuest (HARQ) and Adaptive Modulation and Coding (AMC), but also in a communication system supporting various broadcast services, LDPC codes having various codeword lengths are used to support various data rates according to the requirements of the systems.
To support the LDPC codes having various codeword lengths, puncturing and shortening methods may be used. There are several possible shortening methods, one of which inserts ‘0’ or ‘1’ into some of information bits and avoids transmitting the inserted ‘0’ or ‘1’. The puncturing avoids transmitting a portion of a generated codeword. By designing a parity check matrix taking into account all of the puncturing and shortening methods and the structure of a parity check matrix having undergone shortening, its performance may be optimized for a plurality of codeword lengths. Accordingly, research is needed on the design method.